package alo.p6.work5;

import alo.p6.AVLTreeNode;

/**
 * @ClassName Insert
 * @Description 平衡二叉树的插入
 * @Author Fanxc
 * @DATE 2021/3/4 15:03
 * @Version 1.0
 */
public class Insert {
    AVLTreeNode insert(AVLTreeNode root,AVLTreeNode parent,int data){
        Height Height=new Height();
        Rotate Rotate = new Rotate();
        if (root==null) {
            root=new AVLTreeNode();
            root.setData(data);
            root.setHeight(0);
            root.setLeft(null);
            root.setRight(null);
            return root;
        }else if (data<root.getData()) {
            root.setLeft(insert(root.getLeft(), root, data));
            if (Height.height(root.getLeft()) - Height.height(root.getRight()) == 2) {
                if (data < root.getLeft().getData()) {
                    root = Rotate.singleRotateLeft(root);
                } else {
                    root = Rotate.doubleRotateWithLeft(root);
                }
            }
        }else if (data>root.getData()){
            root.setRight(insert(root.getRight(), root, data));
            if (Height.height(root.getRight()) - Height.height(root.getLeft()) == 2) {
                if (data < root.getRight().getData()) {
                    root = Rotate.singleRotateRight(root);
                } else {
                    root = Rotate.doubleRotateWithRight(root);
                }
            }
        }
        //修正高度
        root.setHeight(Math.max(Height.height(root.getLeft()),Height.height(root.getRight()))+1);
        return root;
    }


}
